package leetcode.editor.cn;

import org.junit.Test;

import javax.swing.tree.TreeNode;
import java.util.*;

public class test {



    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    class levelDeque extends ArrayDeque{
        int level;
    }
    public class Solution {
        public ListNode detectCycle(ListNode head) {
            if (head == null || head.next == null) return null;
            ListNode slow, fast;
            slow = head;
            fast = head;
            while (true) {
                slow = slow.next;
                fast = fast.next;
                if (fast == null) {
                    return null;
                }
                fast = fast.next;
                if (fast == slow) break;
            }
            slow = head;
            while (slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    }

    public Node copyRandomList(Node head) {
        Map<Node,Node> map=new HashMap<>();
        Node p=head;
        while(p!=null){
            Node copy=new Node(p.val);
            map.put(head,p);
            //set next
            if(p.next!=null&&!map.containsKey(p.next)) {
                copy.next=new Node(p.next.val);
                map.put(p.next,copy.next);
            }else
                copy.next=map.get(p.next);
            if(p.random!=null&&!map.containsKey(p.random)) {
                copy.random=new Node(p.random.val);
                map.put(p.random,copy.random);
            }else
                copy.random=map.get(p.random);
            p=p.next;
        }
        return map.get(head);
    }

    @Test
    public void test2() {
        Deque<TreeNode> stack=new ArrayDeque<>();

        Node node1 = new Node(3);
        Node node2 = new Node(2);
        Node node3 = new Node(0);
        Node node4 = new Node(-4);
        Node node5 = new Node(3);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
//        node4.next = node2;
        System.out.println(copyRandomList(node1));
        List<List<Integer>> list=new ArrayList<>();
        Deque<Integer> queue=new ArrayDeque<>();
        queue.push(0);
        queue.push(1);
        queue.push(2);
        queue.pop();
        int[] inorde={1,2};
        int a=inorde.length;
    }

    @Test
    public void test() {
        ListNode node1 = new ListNode(3);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(0);
        ListNode node4 = new ListNode(-4);
        ListNode node5 = new ListNode(3);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node2;
        System.out.println(new Solution().detectCycle(node1).val);
        List<ListNode> l = new LinkedList<>();

    }
}
